package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC169 {

    public int majorityElement(int[] arr) {
        int count = 0;
        int candidate = 0;
        for (int i = 0; i < arr.length; i++) {
            if (count == 0) {
                candidate = arr[i];
            }
            if (arr[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        LC169 an = new LC169();
        int[] arr = {2, 2, 1, 1, 1, 3, 8, 2, 2, 2, 2, 3, 4, 5, 6, 7, 2, 2};

        System.out.println(an.majorityElement(arr));
    }
}
